#include <stdio.h>
#include <malloc.h>
#include <windows.h>
typedef struct{
	float coef;//系数
	int expn;//指数
}ElemType;

typedef struct LNode  
{
	ElemType data;
	struct LNode *next;		//指向后继结点
} LinkList;					//声明单链表结点类型

void CreateListR(LinkList *&L,ElemType a[],int n)
//尾插法建立单链表  //升序插入
{
	LinkList *s,*r;
	L=(LinkList *)malloc(sizeof(LinkList));  	//创建头结点
	L->next=NULL;
	r=L;					//r始终指向终端结点,开始时指向头结点
	for (int i=0;i<n;i++)
	{	
		s=(LinkList *)malloc(sizeof(LinkList));//创建新结点s
		s->data=a[i];
		r->next=s;			//将结点s插入结点r之后
		r=s;
	}
	r->next=NULL;			//终端结点next域置为NULL
}


void InitList(LinkList *&L)
{
	L=(LinkList *)malloc(sizeof(LinkList));  	//创建头结点
	L->next=NULL;
}


void DestroyList(LinkList *&L)
{
	if (L->next == NULL) return; // 处理空链表的情况
	
	LinkList *pre = L; // 假设 L 是头节点
	LinkList *p = pre->next;
	
	while (p != NULL)
	{
		free(pre); // 释放当前节点
		pre = p;   // 将 pre 移动到当前节点
		p = p->next; // 更新 p 到下一个节点
	}
	
	free(pre); // 释放最后一个节点
	L = NULL;  // 设置 L 为 NULL，避免悬挂指针
}



void DispList(LinkList *L)
{
	LinkList *p=L->next;
	while (p!=NULL)
	{	printf("指数：%-2d 系数：%-5.2f\n",p->data.expn,p->data.coef);
		p=p->next;
	}
	printf("\n\n");
}

bool ListInsert(LinkList *&L,int n,float f)
{
	LinkList *p=L->next,*s = L;
	while (p!=NULL)		
	{	
		if(p->data.expn==n)
		{
			p->data.coef = p->data.coef + f;
			return true;
		}
		else if(p->data.expn<n)
		{
			s = s->next;
			p=p->next;
		}
		
		else if(p->data.expn>n&&s->data.expn<n)
		{
			LinkList* m = (LinkList*)malloc(sizeof(LinkList));
			m->data.expn = n;
			m->data.coef = f;
			s->next = m;
			m->next = p;
			return true;
		}
		
	}
	LinkList* q = (LinkList*)malloc(sizeof(LinkList));
	q->data.expn = n;
	q->data.coef = f;
	s->next = q;
	q->next = NULL;
	return true;

	
	
}


bool ListDelete(LinkList *&L,int n)
{
	//按照指数位置删除
	if(L==NULL) return false;
	LinkList *p=L,*s = NULL;
	while (p->next!=NULL)		
	{	
		if(p->next->data.expn==n)
		{
			if(p->next->next!=NULL)
			{
				s = p->next;
				p->next = p->next->next;
				free(s);
				return true;
			}
			else if(p->next->next==NULL)
			{
				s = p->next;
				p->next = NULL;
				free(s);
				return true;
			}
			
		}
		
		p = p->next;

	}
	return false;
}


LinkList* PolynomialAdd(LinkList* L1, LinkList* L2)
{
	LinkList* L = (LinkList*)malloc(sizeof(LinkList)); // 创建新的链表
	L->next = NULL; // 初始化为空
	LinkList* Head = L; // 保存头指针
	
	if (L1->next == NULL) return L2; // L1 为空，返回 L2
	if (L2->next == NULL) return L1; // L2 为空，返回 L1
	
	LinkList* p1 = L1->next; // 跳过头节点
	LinkList* p2 = L2->next; // 跳过头节点
	
	while (p1 != NULL && p2 != NULL)
	{
		if (p1->data.expn == p2->data.expn)
		{
			// 指数相同，合并系数
			float new_coef = p1->data.coef + p2->data.coef;
			if (new_coef != 0)
			{
				L->next = p1; 
				L->next->data.coef = new_coef; 
				L = L->next; 
			}

			
			p1 = p1->next;
			p2 = p2->next;
		}
		else if (p1->data.expn > p2->data.expn)
		{
			L->next = p2; // 添加 p2 节点
			L = L->next;
			p2 = p2->next;
		}
		else
		{
			L->next = p1; // 添加 p1 节点
			L = L->next;
			p1 = p1->next;
		}
	}
	
	// 添加剩余的节点
	if (p1 == NULL) L->next = p2;
	if (p2 == NULL) L->next = p1;
	return Head; // 返回新链表的头部
}

	



int main()
{
	ElemType a1[5] = {0};
	for(int i=0;i<5;i++)
	{
		a1[i].coef = i+5.0;
		a1[i].expn = i;//系数
	}
	LinkList* L1;
	CreateListR(L1,a1,5);
	printf("多项式1：\n");
	DispList(L1);
	
	
	ElemType a2[5] = {0};
	for(int i=0;i<5;i++)
	{
		a2[i].coef = i+5.0;
		a2[i].expn = i;//系数
	}
	LinkList* L2;
	CreateListR(L2,a2,5);
	printf("多项式2：\n");
	DispList(L2);
	fflush(stdout);
	printf("在多项式 1 中插入一个数据:\n");
	ListInsert(L1,8,4.0);
	DispList(L1);
	
	printf("在多项式 2 中删除一个数据:\n");
	ListDelete(L2,1);
	DispList(L2);
	
	
	LinkList* result = PolynomialAdd(L1,L2);
	printf("结果:\n");
	DispList(result);
	
	
	DestroyList(L1);
	DestroyList(L2);

	
	
	return 0;
}
